package com.fr.lintcode;

import org.junit.Test;

public class Q219 {

	/**
	 * @param head: The head of linked list.
	 * @param val:  An integer.
	 * @return: The head of new linked list.
	 */
	public ListNode insertNode(ListNode head, int val) {
		// 插在头部
		if (head == null || head.val >= val) {
			ListNode node = new ListNode(val);
			node.next = head;
			return node;
		}
		ListNode tmp = head;
		while (tmp != null) {
			if (tmp.val < val) {
				// 插入
				if (tmp.next == null || tmp.next.val >= val) {
					ListNode ln = tmp.next;
					ListNode node = new ListNode(val);
					tmp.next = node;
					node.next = ln;
					break;
				}else {
					tmp = tmp.next;
				}
			}else if(tmp.val == val){
				ListNode ln = tmp.next;
				ListNode node = new ListNode(val);
				tmp.next = node;
				node.next = ln;
				break;
			}else {
				tmp = tmp.next;
			}
		}
		return head;
	}

	@Test
	public void testInsertNode() {
		ListNode node = ListNode.build(5, 2);
		System.out.println(insertNode(node, 10));
	}

}
